package nowCoder;

/**
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
 * 
 * @author Ghost
 *
 */
class RandomListNode {
	int label;
	RandomListNode next = null;
	RandomListNode random = null;

	RandomListNode(int label) {
		this.label = label;
	}
}

public class Clone {

	public RandomListNode Clone(RandomListNode pHead) {
		if(pHead==null)
			return null;
		RandomListNode current = pHead;
		RandomListNode tmp;
		while (current != null) {
			tmp = new RandomListNode(current.label);
			tmp.next = current.next;
			current.next = tmp;
			current = tmp.next;
		}     

		current = pHead;
		RandomListNode newHead = pHead.next;
		while (current != null) {
			tmp = current.next;
			if (current.random != null) {
				tmp.random = current.random.next;
			}
			current = tmp.next;
			
		}
		
		current = pHead;

		while (current != null) {
			tmp = current.next;
			current.next = tmp.next;
			current = current.next;
			if(tmp.next!=null){
				tmp.next = tmp.next.next;
			}
		}
		return newHead;
	}

	public static void main(String[] args) {
		Clone clone = new Clone();
		RandomListNode one = new RandomListNode(0);
		RandomListNode two = new RandomListNode(1);
//		RandomListNode three = new RandomListNode(2);
//		RandomListNode four = new RandomListNode(3);
//		RandomListNode five = new RandomListNode(4);

		one.next = two;
//		two.next = three;
//		three.next = four;
//		four.next = five;
//
//		one.random = three;
//		three.random = one;
		one.random = one;
		two.random = one;
		RandomListNode newHead = clone.Clone(one);
		while (newHead != null) {
			System.out.println(newHead + "--" + newHead.next + "--"
					+ newHead.random);
			newHead = newHead.next;
		}

	}
}
